package Leetcode.网格图;

import java.util.Arrays;

/**
 * @Author: kirito
 * @Date: 2024/4/30 13:47
 * @Description:
 * 统计封闭岛屿的数目
 * 中等
 * 相关标签
 * 相关企业
 * 提示
 * 二维矩阵 grid 由 0 （土地）和 1 （水）组成。岛是由最大的4个方向连通的 0 组成的群，封闭岛是一个 完全 由1包围（左、上、右、下）的岛。
 *
 * 请返回 封闭岛屿 的数目。
 *
 *
 *
 * 示例 1：
 *
 *
 *
 * 输入：grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
 * 输出：2
 * 解释：
 * 灰色区域的岛屿是封闭岛屿，因为这座岛屿完全被水域包围（即被 1 区域包围）。
 * 示例 2：
 *
 *
 *
 * 输入：grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]]
 * 输出：1
 * 示例 3：
 *
 * 输入：grid = [[1,1,1,1,1,1,1],
 *              [1,0,0,0,0,0,1],
 *              [1,0,1,1,1,0,1],
 *              [1,0,1,0,1,0,1],
 *              [1,0,1,1,1,0,1],
 *              [1,0,0,0,0,0,1],
 *              [1,1,1,1,1,1,1]]
 * 输出：2
 *
 *
 * 提示：
 *
 * 1 <= grid.length, grid[0].length <= 100
 * 0 <= grid[i][j] <=1
 */

public class closedIsland {
    public static void main(String[] args) {
        int[][] grid =
                {{1,1,1,1,1,1,1},
                {1,0,0,0,0,0,1},
                {1,0,1,1,1,0,1},
                {1,0,1,0,1,0,1},
                {1,0,1,1,1,0,1},
                {1,0,0,0,0,0,1},
                {1,1,1,1,1,1,1}};
        System.out.println(new closedIsland().closedIsland(grid));
    }

    private int m, n;
    private boolean[][] visited;
    /**
     * 跟飞地有点像，先判断边界的土地，如果跟边界土地相连那么就不是封闭
     * @param grid
     * @return
     */
    public int closedIsland(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        visited = new boolean[m][n];
        //边界土地
        for (int i = 0; i < m; i++) {
            dfs(grid, i, 0);
            dfs(grid, i, n - 1);
        }
        for (int j = 1; j < n - 1; j++) {
            dfs(grid, 0, j);
            dfs(grid, m - 1, j);
        }
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0 && !visited[i][j]) {
                    dfs(grid, i, j);
                    ans++;
                }
            }
        }
        return ans;

    }

    public void dfs(int[][] grid, int row, int col) {
        if (row < 0
        || row >= m
        || col < 0
        || col >= n
        || grid[row][col] == 1
        || visited[row][col]) {
            return;
        }
        visited[row][col] = true;
        dfs(grid, row - 1, col);
        dfs(grid, row + 1, col);
        dfs(grid, row, col - 1);
        dfs(grid, row, col + 1);
    }

    /**
     * https://leetcode.cn/link/?target=https%3A%2F%2Fwww.bilibili.com%2Fvideo%2FBV16t421c7GB%2F
     * 数学思维，找每一行每一列有多少1 然后*
     */
    public long numberOfRightTriangles(int[][] grid) {
        int n = grid[0].length;
        //列元素和  多少个1
        int[] colSum = new int[n];
        Arrays.fill(colSum, -1); // 提前减一
        for (int[] row : grid) {
            for (int j = 0; j < n; j++) {
                colSum[j] += row[j];
            }
        }

        long ans = 0;
        //遍历每一行  然后每列，已知每列1的个数，*该行的1个数即可，累加
        for (int[] row : grid) {
            int rowSum = -1; // 提前减一
            //行和  行1的个数
            for (int x : row) {
                rowSum += x;
            }
            for (int j = 0; j < row.length; j++) {
                if (row[j] == 1) {
                    ans += (long) rowSum * colSum[j];
                }
            }
        }
        return ans;
    }

    /**
     * https://leetcode.cn/problems/maximum-points-inside-the-square/?envType=daily-question&envId=2024-08-03
     * @param points    点
     * @param s 字母
     * @return  0
     */
    public int maxPointsInsideSquare(int[][] points, String s) {
        // 初始化一个数组来存储每个字符对应的最小曼哈顿距离，初始值设为最大整数
        int[] minD = new int[26];
        Arrays.fill(minD, Integer.MAX_VALUE);
        // 初始化次小距离为最大整数
        int min2 = Integer.MAX_VALUE;

        // 遍历每个点
        for (int i = 0; i < points.length; i++) {
            // 计算当前点到原点的最大坐标距离（曼哈顿距离）
            int d = Math.max(Math.abs(points[i][0]), Math.abs(points[i][1]));
            // 计算当前点对应的字符在字符串s中的索引
            int c = s.charAt(i) - 'a';

            // 如果当前距离小于之前记录的最小距离
            if (d < minD[c]) {
                // 更新次小距离为之前的最小距离
                min2 = Math.min(min2, minD[c]);
                // 更新最小距离为当前距离
                minD[c] = d;
            } else {
                // 如果当前距离不是最小的，它可能是次小的，因此尝试更新次小距离
                min2 = Math.min(min2, d);
            }
        }

        // 初始化答案计数器
        int ans = 0;
        // 遍历每个字符的最小距离
        for (int d : minD) {
            // 如果某个字符的最小距离小于次小距离，则它可以被包括在答案中
            if (d < min2) {
                ans++;
            }
        }
        // 返回可以包括在正方形内的点的数量
        return ans;
    }
}
